%\documentclass{beamer}
\documentclass[xcolor=dvipsnames,10pt]{beamer}
%\usetheme{Warsaw}
\usetheme{AnnArbor}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{array}
\usepackage{graphicx}
%\usepackage{setspace}

\title{Avaliação dos Threads da Biblioteca Apache Portable Runtime em Sistemas Operacionais de Propósito Geral}
%\subtitle{Introduction to creating presentations in \LaTeX{}using beamer class}
%\author{Edwin Luis Choquehuanca Mamani \\ \textit{edwinchm@icmc.usp.br}}
\author{Edwin Luis Choquehuanca \\ Diego L. Função \\ Dráusio Rossi }
\institute{Instituto de Ciências Matemáticas e de Computação \\ UNIVERSIDADE DE SÃO PAULO }
\date{\today}
\begin{document}
\maketitle

\section{Sumário}
\begin{frame}{Roteiro}
	\tableofcontents
\end{frame}

\section{Introdução}
\begin{frame}{}
\begin{abstract}
\label{resumo}
Este trabalho tem como objetivo analisar o desempenho dos threads fornecidos pela biblioteca \emph{Apache Portable Runtime} num conjunto de sistemas operacionais de propósito geral. Foi desenvolvida uma ferramenta para executar e avaliar os threads nos sistemas operacionais, utiliza-se um algoritmo \emph{CPU-Bound} para os experimentos e como métrica o tempo de resposta de cada execução. 
\end{abstract}
\end{frame}


\begin{frame}{Contextualização}
\begin{itemize}
\item Neste trabalho avalia threads fornecidos pela biblioteca APR\cite{apr} em diferentes sistemas operacionais de propósito geral 
\item Ela fornece uma interface de programação para a utilização  de threads. Para saber qual é o melhor jeito de conseguir o objetivo de paralelizar.
\item Uma opção para usar os recursos da tecnologia multi-núcleo e a biblioteca Apache Portable Runtime\cite{apr}.
\item Para isto vamos utilizar uma ferramenta que possa criar threads do tipo CPU Bound e como métrica de avaliação utilizaremos os tempos de resposta da execução dos experimentos nos diferentes sistemas operacionais.
\end{itemize}
\end{frame}

\begin{frame}{Objetivos}
\begin{itemize}
\item Avaliar os threads fornecidas pela biblioteca APR\cite{apr}.
\item Avaliar o desempenho dos threads em alguns sistemas operacionais de propósito gerais.
\item Analisar o desempenho dos threads sob as arquiteturas multi-core e multiprocessador.
\end{itemize}
\end{frame}


%==============================================================================================
\section{Fundamentação Teórica}


\subsection{Threads}
\begin{frame}{Threads ao nível do usuário e do núcleo}
Há três modelos de implementação de threads:
\begin{itemize}
\item Threads ao nível do usuário ou aplicação;
\item Threads ao nível do núcleo;
\item Thread híbrido.
\end{itemize}
\end{frame}

\begin{frame}{Nível do usuário ou aplicação}
\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth]{../img/thread-user}
\caption{\textit{Threads ao nível do usuário ou aplicação\cite{cameron}.}}
\label{t-user}
\end{figure}
\end{frame}


\begin{frame}{Threads ao nível do núcleo}
\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth]{../img/thread-kernel}
\caption{\textit{Threads ao nível do núcleo\cite{cameron}.}}
\label{t-kernel}
\end{figure}
\end{frame}


\subsection{Processadores multi-core}
\begin{frame}{Multi-core com cache L2 separado e L2 partilhada}
\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth]{../img/l2-share}
\caption{\textit{Processador multi-core com cache L2 separado e processador multi-core com  L2 partilhada\cite{domeika}.}}
\label{l2share}
\end{figure}
\end{frame}

\begin{frame}{Multi-core simétrico e assimétrico}
\begin{itemize}
\item No multiprocessamento simétrico (SMP):
\begin{itemize}
\item Têm visões semelhantes do sistema e assim compartilham a memória principal. 
\item Os valores fornecidos na memória principal podem ser acessados e modificados por cada um dos núcleos do processador. 
\end{itemize}
\item No multiprocessamento assimétrico (AMP)
\begin{itemize}
\item A visão do sistema é diferente entre os núcleos do processador. 
\item Dois núcleos do processador não podem acessar diretamente e modificar a mesma posição de memória.
\end{itemize}
\end{itemize}
\end{frame}


\subsection{Apache Portable Runtime}
\begin{frame}{Plataformas suportadas}
Atualmente as plataformas suportadas são:
\begin{itemize}
\item Variantes do UNIX (Linux, FreeBSD, OpenBSD, etc.);
\item Windows;
\item Netware;
\item Mac OSX;
\item OS/2.
\end{itemize}
\end{frame}

\begin{frame}{Carateristicas}
Para dar um breve resumo, a versão atual da biblioteca APR é 1.3 incluem o seguinte:
\begin{itemize}
\item Operações Atômicas;
\item Carga mediante Dynamic Shared Object(.dlls ou .so);
\item I/O de arquivos e rede;
\item Mutexes, etc);
\item Gestão de memória (alocador de alto desempenho); 
\item Mapeio de Memória para arquivos;
\item Multicast Sockets;
\item Memória partilhada;
\item \textbf{Gerenciamento de threads e processos;}
\item Várias estruturas de dados (tabelas, hashes, filas com prioridade filas, strings, etc).
\end{itemize}
\end{frame}

\subsection{Método de Monte Carlo}
\begin{frame}{Computação de PI}
A área do quadrado é $R^2$, onde $R$ é o comprimento do lado. Um quarto de um círculo é inscrito no quadrado. Seu raio é $r$ e seu centro está na origem do plano $x,y$. A área da quarta parte do círculo é $\frac{{\pi}{R^2}}{4}$.
\begin{figure}[H]
\centering
\includegraphics[width=.35\textwidth]{../img/cuadrado}
\caption{\textit{Quarta parte do círculo.}}
\label{qcirculo}
\end{figure}
\end{frame}

\begin{frame}{Computação de PI}
Considerando a área de $\frac{1}{4}$ de círculo parcialmente representado na figura \ref{qcirculo}, tem-se que:
\begin{block}{Resolução da equação (1)}
\begin{equation}\label{area}
							A = \frac{1}{4}\pi{R^2}
\end{equation}
\end{block}

Pelo Método de Monte Carlo,
\begin{block}{Resolução da equação (2)}
\begin{equation}\label{montecarloeq}
							A = L^2\frac{P_{in}}{P_{total}}
\end{equation}
\end{block}
\end{frame}

\begin{frame}{Computação de PI}
$$\frac{1}{4}\pi{R^2} = L^2\frac{P_{in}}{P_{total}}$$
$$\pi = \frac{L^2\frac{P_{in}}{P_{total}}}{\frac{1}{4}{R^2}}$$

Considerando-se $L=R=1$ obtém-se:
\begin{block}{Equação}
\begin{equation}
	\pi = 4\frac{P_{in}}{P_{total}}
\end{equation}
\end{block}
\end{frame}


\begin{frame}{Algoritmo para implementar}
\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth]{../img/alg}
%\caption{\textit{Quarta parte do círculo.}}
%\label{qcirculo}
\end{figure}
\end{frame}

%==============================================================================================
\section{Cenário}
\subsection{Ambiente}
\begin{frame}{Software}
Foram utilizados os seguintes elementos:
\begin{itemize}
\item Sistema Operacional Linux; Kernel 2.6.28, distribuição Ubuntu 9.04.
	\begin{itemize}
	\item Compilador GCC, versão 4.3.3.
	\end{itemize}
\item Sistema Operacional FreeBSD; Kernel 7.2-1, FreeBSD 7.2.
	\begin{itemize}
	\item Compilador GCC, versão 4.2.1.
	\end{itemize}
\item Sistema Operacional Windows; Compilação 7100, Windows 7.
	\begin{itemize}
	\item Visual Studio SP1, versão 2005.
	\end{itemize}
\item Biblioteca Apache Portable Runtime, versão 1.3.3.
\end{itemize}
\end{frame}

\begin{frame}{Hardware}
Foram utilizados os seguintes elementos:
	\begin{itemize}
		\item Intel Core 2 Quad (Q6600) com clock de 2.4Ghz, 4MB de memória cache;
		\item 3GB de memória principal;
	\end{itemize}
\end{frame}

\subsection{Ferramenta de avaliação}
\begin{frame}{Ferramenta}
Foi desenvolvida uma aplicação para fazer os experimentos, baseada na biblioteca  APR\cite{apr},  de entre as características da aplicação temos:
\begin{itemize}
\item Mudanças na carga de trabalho;
\item Número de experimentos;
\item Coleta dos tempos de execução;
\item Funções estatísticas: média, desvio padrão, etc.
\end{itemize}
Esta ferramenta foi desenvolvida na linguagem de programação C++ e está disponibilizada no endereço \href{http://code.google.com/p/apr-threads/}{http://code.google.com/p/apr-threads/}.
\end{frame}

\begin{frame}{Diagrama de classes}
Este diagrama está baseado num Padrão de Projeto \cite{gamma}, especificamente o padrão  ``Strategy''.
\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth]{../img/diagrama}
\caption{\textit{Diagrama de classes.}}
\label{dclasses}
\end{figure}
\end{frame}

\subsection{Avaliação}
\begin{frame}{Fatores da Avaliação}
A avaliação é composta dos seguintes fatores:
\begin{itemize}
\item Quantidade de threads que executará a ferramenta;
\item O sistema operacional.
\end{itemize}
\end{frame}

\begin{frame}{Níveis da avaliação}
A avaliação é composta dos seguintes níveis:
\begin{itemize}
\item Número de threads (1, 2, 4, 8,..., 1024);
\item 3 Sistemas operacionais.
\end{itemize}
\begin{block}{Número de experimentos}
$$n = 11 * 3 = 33$$
$$30 * n = 990$$
\end{block}
\end{frame}

\begin{frame}{Níveis da avaliação}

\begin{table}[H]
	\begin{center}
	\begin{tabular}{|c|l|l|l|}
	\hline 
	\textbf{$i, j$}	&\textbf{Windows}	&\textbf{FreeBSD}	&\textbf{GNU/Linux}	\\
	\hline 	\hline 
	1 	&Tempo $X_{1,1}$ 	&Tempo $X_{1,2}$ 	&Tempo $X_{1,3}$	\\
	\hline 
	2 	 &Tempo $X_{2,1}$	&Tempo $X_{2,2}$	&Tempo $X_{2,3}$ 	\\
	\hline 
	4	 &Tempo $X_{3,1}$	&Tempo $X_{3,2}$	&Tempo $X_{3,3}$	\\
	\hline 
	8	 &Tempo $X_{4,1}$	&Tempo $X_{4,2}$	&Tempo $X_{4,3}$	\\
	\hline 
	16  &Tempo $X_{5,1}$	&Tempo $X_{5,2}$	&Tempo $X_{5,3}$	\\
	\hline 
	32	 &Tempo $X_{6,1}$	&Tempo $X_{6,2}$	&Tempo $X_{6,3}$	\\
	\hline 
	64	 &Tempo $X_{7,1}$	&Tempo $X_{7,2}$	&Tempo $X_{7,3}$	\\
	\hline 
	128 &Tempo $X_{8,1}$	&Tempo $X_{8,2}$	&Tempo $X_{8,3}$	\\
	\hline 
	256 &Tempo $X_{9,1}$	&Tempo $X_{9,2}$	&Tempo $X_{9,3}$	\\
	\hline 
	512 &Tempo $X_{10,1}$	&Tempo $X_{10,2}$	&Tempo $X_{10,3}$	\\
	\hline 
	1024	&Tempo $X_{11,1}$	&Tempo $X_{11,2}$	&Tempo $X_{11,3}$ \\
	\hline 
	\end{tabular}
		\end{center}
	\caption{\textit{Tabela de Avaliações.}}
	\label{tm_exp}
	\end{table}
\begin{itemize}
\item $i$: quantidade de threads por experimento;
\item $j$: sistema operacional usado para o experimento ($FreeBSD=1, GNU/Linux=2, Windows=3$).
\end{itemize}
\end{frame}
%==============================================================================================

\section{Resultados} 
\subsection{Resultados obtidos}
\begin{frame}{FreeBSD}
Sistema operacional FreeBSD 7.2:
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/freebsd}
\caption{\textit{Threads da APR no FreeBSD.}}
\label{gfreebsd}
\end{figure}
\end{frame}

\begin{frame}{FreeBSD}
Sistema operacional FreeBSD 7.2:
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|l|l|l|}
\hline 
\textbf{Threads}	&\textbf{M. T. Resposta (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança} \\ \hline \hline
1	&216,03	&0,18				&0,07\\ \hline
2	&108,07	&0,25				&0,09\\ \hline
4	&63,83		&20,21				&7,23\\ \hline
8	&64,23		&7,3				&2,61\\ \hline
16	&56,67		&3,82				&1,37\\ \hline
32	&56,47		&3,12				&1,11\\ \hline
64	&55,77		&1,1				&0,4\\ \hline
128	&55,83		&0,83				&0,3\\ \hline
256	&56,17		&0,38				&0,14\\ \hline
512	&58,37		&0,67				&0,24\\ \hline
1024	&63,63		&1				&0,36\\ \hline
\textbf{Média}	&77,73		&3,53				&1,26\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Resultados dos threads no FreeBSD.}}
\label{results-freebsd}
\end{table}
\end{frame}


\begin{frame}{GNU/Linux}
Sistema operacional Ubuntu 9.04:
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/linux}
\caption{\textit{Threads da APR no Linux.}}
\label{glinux}
\end{figure}
\end{frame}

\begin{frame}{GNU/Linux}
Sistema operacional Ubuntu 9.04:
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|l|l|l|}
\hline 
\textbf{Threads}	&\textbf{M. T. Resposta (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança} \\ \hline \hline
1	&290,73		&15,27				&5,46\\ \hline
2	&150,33		&16,42				&5,88\\ \hline
4	&79,8		&13,39				&4,79\\ \hline
8	&96,4		&14,64				&5,24\\ \hline
16	&123,1		&18,56				&6,64\\ \hline
32	&148,3		&22,5				&8,05\\ \hline
64	&164,83		&13,32				&4,76\\ \hline
128	&177,63		&9,4				&3,36\\ \hline
256	&192,33		&11,97				&4,28\\ \hline
512	&205,83		&8,83				&3,16\\ \hline
1024	&218		&5,65				&2,02\\ \hline
\textbf{Média}	&167,94		&13,63				&4,88\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Resultados dos threads no GNU/Linux.}}
\label{results-linux}
\end{table}
\end{frame}

\begin{frame}{Windows}
Sistema operacional Windows 7RC:
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/windows}
\caption{\textit{Threads da APR no Windows.}}
\label{gwindows}
\end{figure}
\end{frame}

\begin{frame}{Windows}
Sistema operacional Windows 7RC:
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|l|l|l|}
\hline 
\textbf{Threads}	&\textbf{M. T. Resposta (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança}\\ \hline \hline
1	&327,67		&11,78				&4,22\\ \hline
2	&332,83		&10,46				&3,74\\ \hline
4	&334,43		&9,05				&3,24\\ \hline
8	&335	   	&8,14				&2,91\\ \hline
16	&329,2		&7,97				&2,85\\ \hline
32	&327,6		&6,45				&2,31\\ \hline
64	&328,1		&5,74				&2,06\\ \hline
128	&327,1		&7,05				&2,52\\ \hline
256	&327,53		&2,92				&1,05\\ \hline
512	&333,4		&7,97				&2,85\\ \hline
1024	&344,5		&4,58				&1,64\\ \hline
\textbf{Média}	&331,58		&7,47				&2,67\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Resultados dos threads no Windows.}}
\label{results-windows}
\end{table}
\end{frame}

\begin{frame}{Resultados gerais}
Os três sistemas operacionais:
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/gfinal}
\caption{\textit{FreeBSD, GNU/Linux, e Windows usando APR.}}
\label{allos}
\end{figure}
\end{frame}


\subsection{Análises comparativas dos resultados}
\begin{frame}{Análises de resultados para 1 thread}
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline 
\textbf{SO}	&\textbf{Média  (ms)}	&\textbf{Desvio padrão}	&\textbf{I. de confiança} \\ \hline \hline
FreeBSD	   &216,03		&0,18				   &0,07\\ \hline
GNU/Linux	&290,73		&15,27				&5,46\\ \hline
Windows	   &327,67		&11,78				&4,22\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Análises dos resultados do programa seqüencial.}}
\label{anali-1t}
\end{table}
\end{frame}

\begin{frame}{Análises de resultados para 1 thread}
\begin{figure}[H]
\centering
\includegraphics[width=1\textwidth]{../img/intv-1t}
\caption{\textit{Intervalo de confiança para o programa seqüencial.}}
\label{intv-1}
\end{figure}
\end{frame}

\begin{frame}{Análises de resultados para 4 threads}
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline 
\textbf{SO}	&\textbf{Média (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança} \\ \hline \hline
FreeBSD	   &63,83		&20,21				&7,23\\ \hline
GNU/Linux	&79,8		&13,39				&4,79\\ \hline
Windows	   &334,43		&9,05				&3,24\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Análises dos resultados 4 thread.}}
\label{anali-4t}
\end{table}
\end{frame}

\begin{frame}{Análises de resultados para 4 threads}
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/intv-4t}
\caption{\textit{Intervalo de confiança para 4 threads.}}
\label{intv-4}
\end{figure}
\end{frame}

\begin{frame}{Análises de resultados para 16 threads}
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline 
\textbf{SO}	&\textbf{Média (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança} \\ \hline \hline
FreeBSD	   &56,67		&3,82				&1,37\\ \hline
GNU/Linux   &123,1		&18,56				&6,64\\ \hline
Windows	   &329,2		&7,97				&2,85\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Análises dos resultados 16 thread.}}
\label{anali-16t}
\end{table}
\end{frame}

\begin{frame}{Análises de resultados para 16 threads}
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/intv-16t}
\caption{\textit{Intervalo de confiança para 16 threads.}}
\label{intv-16}
\end{figure}
\end{frame}


\begin{frame}{Análises de resultados para 128 threads}
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline 
\textbf{SO}	&\textbf{Média (ms)}	&\textbf{Desvio padrão}		&\textbf{I. de confiança} \\ \hline \hline
FreeBSD	   &55,83		&0,83				&0,3\\ \hline
GNU/Linux   &177,63		&9,4				&3,36\\ \hline
Windows	   &327,1		&7,05				&2,52\\ \hline
\end{tabular}
\end{center}
\caption{\textit{Análises dos resultados 128 thread.}}
\label{anali-128t}
\end{table}
\end{frame}

\begin{frame}{Análises de resultados para 128 threads}
\begin{figure}[H]
\centering
\includegraphics[width=.95\textwidth]{../img/intv-128t}
\caption{\textit{Intervalo de confiança para 128 threads.}}
\label{intv-128}
\end{figure}
\end{frame}


%==============================================================================================


\section{Conclusões}
\begin{frame}{Resultados alcançados}
\begin{itemize}
\item Linux tem um comportamento esperado porque a APR usa pthreads\cite{posixthread}.
\item FreeBSD é o ganhador, ele não é afeitado pelo overhead como é no caso do Linux, este fenômeno começa só desde 512 threads para diante.
\item A implementação feita da APR para Windows poderia se falar que é ruim. Para visar que isto não fora por outras causas foram executados experimentos com Windows XP e Windows 7 RC, também mudando a versão da biblioteca de 1.3.3 e 1.3.5 obtendo as mesmas médias de tempo de resposta. 
\item A partir de 8 threads FreeBSD começa melhorando com fator de dois com respeito ao Linux nos tempos de resposta.
\item A biblioteca APR é uma excelente ferramenta para a programação de threads em ambientes UNIX.
\item FreeBSD é quase seis vezes melhor que o Windows desde 4 threads até 1024 threads.
\item O uso de variáveis ``\textbf{static}'' no código compartilhado pelos threads é um factor critico.
\end{itemize}
\end{frame}

\begin{frame}{Sugestões para trabalho futuro}
\begin{itemize}
\item Tendo em conta que a APR implementa seu threads usando os métodos nativos de cada sistema operacional e apresenta uma abstração para o programador. Fica como uma tarefa futura; conferir os resultados com um programa que faca o mesmo que o programa construído na avaliação, com a diferença de não utilizar a biblioteca sino os métodos nativos do Windows.
\item Compilar APR com o compilador GCC para Windows.
\item Inclusão de outros sistemas operacionais e de outros tipos de algoritmos não só CPU Bound.
\item Melhora da ferramenta de avaliação para obter resultados mais rapidamente.

\end{itemize} 
\end{frame}

\section{Referências}
\begin{thebibliography}{9}
\bibitem{apr} The Apache Software Foundation, ``Apache Poratble Runtime'', visitado em 26 de Junho de 2009 - 16:23, Disponibilizado: \href{http://apr.apache.org}{http://apr.apache.org}.
\bibitem{domeika} Domeika Max . ``Software Development for Embedded Multi-core Systems - A Practical Guide Using Embedded Intel Architecture''. 2008.
\bibitem{gamma} Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, ``Design Patterns: Elements of Reusable Object-Oriented Software'', 1995.
\bibitem{cameron} Cameron Hughes, Tracey Hughes. ``Professional Multicore Programming Design and Implementation for C++ Developers''. Wiley Publishing, Inc. 2008.
\bibitem{posixthread} The UNIX\textregistered System. ``POSIX Threads Programming''. Visitado em 1 de Julho de 2009 - 16:10. Disponibilizado: \href{http://www.unix.org/single\_unix\_specification}{http://www.unix.org/single\_unix\_specification}
\end{thebibliography}
\end{document}


